package com.lw.leetcode.other.c;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 1354. 多次求和构造目标数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/16 17:39
 */
public class IsPossible {

    public static void main(String[] args) {
        IsPossible test = new IsPossible();

        // true
//        int[] arr = {9, 3, 5};

        // false
//        int[] arr = {1, 1, 1, 2};

        // true
//        int[] arr = {8, 5};

        // true
//        int[] arr = {16, 37, 55, 1};

        // false
//        int[] arr = {16, 37, 55, 2};

        // false
        int[] arr = {1, 1000000000};

        boolean possible = test.isPossible(arr);
        System.out.println(possible);
    }

    public boolean isPossible(int[] target) {
        int length = target.length;
        if (length == 1) {
            return target[0] == 1;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        long sum = 0;
        for (int i : target) {
            sum += i;
            queue.add(i);
        }
        while (sum > length) {
            int m = queue.poll();
            long other = sum - m;
            long n = (m + other - 1) / other - 1;
            if (n < 1) {
                return false;
            }
            int v = (int) (m - n * other);
            if (v < 1) {
                return false;
            }
            queue.add(v);
            sum = other + v;
        }
        return sum == length;
    }

}
